﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<vector>
#include<iostream>

using namespace std;

//用哈希表的思想，在结合正负数分开两种类型进行区分
//⾯试题17.19.消失的两个数字
//class Solution {
//public:
//    vector<int> missingTwo(vector<int>& nums) {
//        int n = nums.size(), m = n + 2, t = nums[0];
//        nums.push_back(0x3f3f3f3f);
//        nums.push_back(0x3f3f3f3f);
//        nums.push_back(0x3f3f3f3f);
//        for (int i = 0; i < n; ++i) {
//            int x = abs(nums[i]);
//            if (x <= m) nums[x] = -nums[x];
//        }
//        vector<int> ans;
//        for (int i = 1; i <= m; ++i) if (nums[i] >= 0) ans.push_back(i);
//        return ans;
//    }
//};
//class Solution {
//public:
//    string modifyString(string s) {
//        int haxi = 0;
//        for (int i = 0; i < s.size(); i++)
//        {
//            if (i != '?')
//            {
//                haxi |= (1 << (s[i] - 'a'));
//            }
//        }
//        int j = 0;
//        for (int i = 0; i < s.size(); i++)
//        {
//            if (s[i] == '?')
//            {
//                while ((i >> j) & 1)
//                    s[i] = j + 'a';
//            }
//        }
//        return s;
//    }
//};
//欠考虑
//class Solution {
//public:
//    string modifyString(string s) {
//        int haxi = 0;
//        for (int i = 0; i < s.size(); i++)
//        {
//            if (s[i] != '?')
//            {
//                haxi |= 1 << (s[i] - 'a');
//            }
//        }
//        int j = 0;
//        for (int i = 0; i < s.size(); i++)
//        {
//            if (s[i] == '?')
//            {
//                while ((haxi >> j) & 1 == 1)
//                    j++;
//                s[i] = j + 'a';
//                haxi |= 1 << (s[i] - 'a');
//            }
//        }
//        return s;
//    }
//};

//替换所有的问号（easy）
//考虑重复，只需要考虑左右，用a，b，c三个字母来进行互不重复即可
class Solution {
public:
    string modifyString(string s) {
        int n = s.size();
        for (int i = 0; i < n; i++)
        {
            if (s[i] == '?')
            {
                for (int j = 0; j < 3; j++)
                {
                    //排除a，b，c中的两个
                    if ((i && s[i - 1] == 'a' + j) || (i + 1 < n && s[i + 1] == 'a' + j)) continue;
                    s[i] = 'a' + j;
                    break;
                }
            }
        }
        return s;
    }
};

int main()
{
    Solution a;
    string s = "?zs";
    a.modifyString(s);
    //vector<int> v = { 1 ,3};
    //a.missingTwo(v);*/
  	return 0;
}